package com.example.question.tree.tree1;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Date 2023-07-09
 * @Author Jonathan
 */
public class Code10_404 {

    public static void main(String[] args) {
        TreeNode tree = Tree.createTree(new Integer[]{3, 9, null, null, 20, 15, null, null, 7, null, null});
        Code10_404 code = new Code10_404();
        System.out.println(code.sumOfLeftLeaves3(tree));
    }

    private int sum = 0;

    public int sumOfLeftLeaves2(TreeNode root) {
        process(root, false);
        return sum;
    }

    public int sumOfLeftLeaves(TreeNode root) {
        return process(root, root);
    }

    public int sumOfLeftLeaves3(TreeNode root) {
        return process(root).leftLeaveSum;
    }

    /**
     * 直接将父节点传下去 就能判断当前节点是不是左孩子了  高  实在是高！！！
     *
     * @param node
     * @param parent
     * @return
     */
    private int process(TreeNode node, TreeNode parent) {
        if (node == null) return 0;
        if (node.left != null && node.right != null && parent.left == node) {
            return node.val;
        }
        int left = process(node.left, node);
        int right = process(node.right, node);
        return left + right;
    }


    private void process(TreeNode node, boolean isLeft) {
        if (node == null) return;
        if (node.left == null && node.right == null && isLeft) {
            sum += node.val;
        }
        process(node.left, true);
        process(node.left, false);

    }



    private Helper process(TreeNode node) {
        if (node == null) {
            return null;
        }
        Helper left = process(node.left);

        Helper right = process(node.right);


        boolean isLeave = left == null && right == null;
        if (isLeave) {
            return new Helper(true, 0);
        }

        if (right == null) {
            int leftLeaveSum = left.isLeave ? node.left.val : left.leftLeaveSum;
            return new Helper(false, leftLeaveSum);
        }

        if (left == null) {
            return new Helper(false, right.leftLeaveSum);
        }
        // 都不为null
        int sum = left.isLeave ? (node.left.val + right.leftLeaveSum) : (left.leftLeaveSum + right.leftLeaveSum);
        return new Helper(false, sum);
    }

    static class Helper {
        boolean isLeave;
        int leftLeaveSum;

        public Helper(boolean isLeave, int leftLeaveSum) {
            this.isLeave = isLeave;
            this.leftLeaveSum = leftLeaveSum;
        }
    }


    /**
     * 层次遍历
     *
     * @param root
     * @return
     */
    public int sumOfLeftLeaves1(TreeNode root) {
        if (root == null) return 0;
        Queue<Info> queue = new LinkedList<>();
        queue.offer(new Info(root, false));
        int sum = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Info info = queue.poll();
                if (info.node.right == null && info.node.left == null && info.left) {
                    sum += info.node.val;
                }
                if (info.node.left != null) {
                    queue.offer(new Info(info.node.left, true));
                }
                if (info.node.right != null) {
                    queue.offer(new Info(info.node.right, false));
                }
            }
        }
        return sum;
    }

    static class Info {
        TreeNode node;
        boolean left;

        public Info(TreeNode node, boolean left) {
            this.node = node;
            this.left = left;
        }
    }
}
